KURZUS: Alkalmazott operációkutatás

MODUL: I. modul: Az operációkutatás tárgya és módszerei

4. lecke: Programozási feladatok megoldása Solver programmal

|  | Érzékenységvizsgálat
| Tanulási útmutató
| A lineáris és nemlineáris programozási feladatok megoldására és az optimális megoldás utóelemzésére jól felhasználható az Excel táblázatkezelő.
| A Solver program leírását a tankönyvben megtalálja. Kövesse a jegyzet útmutatásait úgy, hogy nyissa meg az Excel táblázatkezelőt. Figyeljen a jegyzetben található szakkifejezésekre! Ezeket jól jegyezze meg.
| Az érzékenységvizsgálat lényegét és eseteit a tankönyv 3.1 és 3.2. fejezetében találja. Ezt elég azután áttanulmányozni, ha az elemzést a számítógépével megvalósította.
| Tevékenységek
| Figyelmesen olvassa el a Solver program leírását. Előre nyissa meg az Excel táblázatkezelő programot, hogy a leírtakat a táblázatkezelőn mindjárt azonosítsa, illetve megvalósítsa. A 3. lecke tanulása során megismerte, hogy mit nevezünk együttható mátrixnak (A), jobb oldal vektorának ( b ¯ ), célfüggvénynek (z) és a változók vektorának ( x ¯ ). Ezeknek megfelelő tartományokat, cellákat kell kijelölni az Excel-táblázaton, és célszerű a képernyőn látható módon elnevezni ezeket. Ha az MSZORZAT (A; x ¯ ) műveletet túl bonyolultnak találja (az is, mert nehéz javítani), akkor ajánlható a képletek cellába való beírása. Pl. H9 cellába ezt beírni: =8*C11+6*C12+2*C13+10*C14+2*C15 majd Enter. A képletek elemeit érdemes rámutatással beírni, mert így kisebb a hiba lehetősége! Hasonlóan lehet az egyenlőtlenség bal oldalának képletét a kijelölt cellába beírni. Ennél is kényelmesebb a SZORZATÖSSZEG függvény használata. ( f x , Mat. és trigonom.) Ha valamelyik legördülő menüben nem ért valamit, akkor bátran használja a Súgót, igen hasznos részletes információt ad a gyakorlati kivitelezéshez és az elmélethez is! A modell adatainak bevitele és a célfüggvény valamint a korlátozó feltételek képleteinek elhelyezése után hívja meg a Solver parancsot. Itt kell értelemszerűen az előzően Excel celláiban elhelyezett képleteket és változókat bejelölni. A Beállítások lenyíló menüben igen fontos bejelölni, hogy Lineáris modellt feltételezünk vagy nem. Hasonlóan fontos (hátha elfelejtettük) a Nemnegatív feltételezés bejelölése, mert ez a változók nemnegatívitását biztosítja. Mint tudja ez a lineáris programozási feladatoknál alapfeltétel! A többi opció beállítása most még nem szükséges. (Súgóban megtalálható a fogalmak definíciója). Ezeket akkor kell beállítani, ha a "Solver nem talál megoldást" című üzenetet kapja. Előfordulhat, hogy azért nem kapott megoldást, mert kevés a beállított idő, vagy túl nagy pontossággal akarja a változó értékeit meghatározni (a Solver közelítő megoldásokat ad!), vagy az egyenlőségeket teljesíteni! Természetesen az is lehet, hogy tényleg nincs optimális megoldás valamilyen a tankönyvben korábban tárgyalt eset miatt. Ha a tankönyvben található példát Ön is sikerrel megoldotta a Solver program segítségével, akkor oldja meg a könyv 1.5.2. fejezetében található, szimplex módszerrel már megoldott feladatot. Ha nehézséget okoz az elhelyezés, akkor a mellékelt "4. téma mintafeladata" Excel-fájlban ezt tanulmányozhatja. Így tudja ellenőrizni, hogy sikeres volt-e az Exceles elképzelése. Természetesen minden feladat megoldása ellenőrizhető: visszahelyettesíti a kapott optimális megoldást az eredeti feladatba. Ha az eddig elmondottakat jól begyakorolta, akkor foglalkozzon az érzékenység- vizsgálattal. Jól jegyezze meg az erőforrások árnyékára és a redukált költség fogalmak jelentőségét és azt, hogyan kell ezt az Érzékenység jelentésből leolvasni. Ezen ismeretek birtokában végezzen Ön is egy érzékenységvizsgálatot! Tegye fel a "Mi lenne, ha..." típusú kérdést a probléma megoldása kapcsán. Pl. Mi lenne, ha az egyik erőforrás kapacitását 5 egységgel megnövelnénk? (Hiszen ezt az erőforrást teljesen kihasználtuk, korlátozza a termelés méretét, a célfüggvény értékét).
| Követelmények
| Meg tudjon oldani egy adott programozási feladatot Solver segítségével. Excel*táblázaton elhelyezett programozási feladatot meg tudjon Solverrel oldani, és válaszolni tudjon a következő típusú kérdésekre: Milyen változtatást kell megtenni a modellen, hogy a programba nem került változó is bekerülhessen? Milyen változtatást kell tennem, hogy az erőforrások szűk keresztmetszetét növeljem és a célfüggvény is a legnagyobb mértékben növekedjék.

|  | Bemutató feladat
| Oldjuk meg Solver segítségével a következő feladatot:
| x 1 , x 2 , x 3 ≥ 0 2 x 1 + x 2 + x 3 ≤ 16 − x 1 + x 2 +2 x 3 = 10 x 1 +2 x 2 + x 3 ≥ 16 z= x 1 +3 x 2 + x 3 → max⁡
| Vigyük be az Excelbe az adatokat az alábbi módon:
| A z* a megoldásvektor lesz, ennek értékei jelenleg nullával egyenlők. A b vektor előtt üresen hagyott oszlopba elő kell állítani az egyenletek algebrai formáját.
| Az E3 oszlopba írjuk be: =SZORZATÖSSZEG(B3:D3;$B$7:$D$7).
| A kapott érték természetesen itt is nulla lesz. Ezt másoljuk be az összes egyenlet sorába (E4; E5).
| Az E6 cellába fogjuk a célfüggvény értékét megkapni, ide most az alábbi kerül: =SZORZATÖSSZEG(B6:D6;$B$7:$D$7)
| Ezután a feladatot oldjuk meg Solverrel. A Solvert az eszközök menüben találjuk meg. Nem automatikus része az Excelnek, külön kell telepíteni. Telepítés után azonban nem működik automatikusan. Az Eszközök menüben, a Bővítménykezelő ablakában be kell jelölni a Solver bővítmény választódobozát.
| Hívjuk meg a Solvert az Eszközök menüből.
1. | Célcellának jelöljük be az E6-t, ekkor az ablakban a következőt látjuk:$E$6
2. | Jelöljük meg a max-t, hiszen a feladat maximumot kér.
3. | A módosuló celláknak jelöljük be a B7;D7-t, ekkor az ablakban megjelenik: $B$7:$D$7
4. | Korlátozó feltételek: egyenként kell felvenni őket:
| $E$3<=$G$3 $E$4=$G$4 $E$5>=$G$5
5. | A Beállítás gombra kattintva bejövő ablakon két dolgot kell megjelölni
| A lineáris modell feltételezése A nem negatív feltételezés
6. | Ezután kattintsunk a megoldás gombra.
7. | A megjelenő ablakba már láthatjuk az eredményt:
8. | Ezután kérdezzük le az Eredményt és az érzékenységjelentést.
| Eredményjelentés:
| A célfüggvény értéke 38. A változók értékénél látható, hogy x3 változó értéke nullával egyenlő, ez azt jelenti, hogy ne szerepeljen a programban. A korlátozó feltételeknél látható, hogy az általunk megadott korlátok mennyire teljesültek.
| Érzékenységjelentés:
1. | Módosuló cellák: A redukált költség oszlopában, amely változó sorában érték van, azt a változót nem vonjuk be a bázisba. AZ oszlopban szereplő értékek megmutatják, hogy miért ne szerepeljen a változó a programban. Ha van érték, az azt jelenti, hogy a célfüggvény értékét ennyivel csökkentené a változó minden egyes egysége. Ez esetünkben 3,667. Hogy ezt elkerüljük, növelni kellene x3 célfüggvénybeli együtthatóját. Jelen esetben legfeljebb 3,667 egységgel. A feladat még optimális marad, de fennáll az alternatív optimum lehetősége. Ez a megengedhető növekedés/csökkenés oszlop jelentése. A redukált költségoszlop értékei minimumfeladatnál pozitív előjelűek, ami azt jelenti, hogy növelnék a minimumot. Maximum feladat esetében negatív előjelűek, mert csökkentenék az optimumot.
2. | Korlátozó feltételek: A Shadow árnyékár azt mutatja meg, hogy ha egy erőforrás korlátozottan áll rendelkezésre, kapacitásának egységnyi változása hogyan változtatja meg a célfüggvény értékét. A megengedhető növekedés/csökkenés oszlopban azokat a határokat látjuk, amelyek között a feltételek jobb oldalán álló kapacitás változhat az adott bázis változatlansága mellett.

|  | Önellenőrző feladatok
| 1. Oldja meg a következő feladatot Solver programmal!
| x 1 , x 2 , x 3 ≥ 0 x 1 +3 x 3 ≥ 6 − x 1 + x 2 + x 3 ≤ 2 x 1 + x 2 + x 3 = 8 z=110 x 1 +50 x 2 +120 x 3 → max⁡
| Javaslom, hogy a B4:D6 tartományba helyezze el az együttható mátrixot, a B7:D7 tartományba a célfüggvény együtthatóit, F4:F6 cellákba a jobb oldal konstansait, a változók értékei a B9-D9 tartományban legyen olvasható, a célfüggvény képletét az F7 cellába írja be. Javaslom, hogy a feltételrendszer bal oldali képleteit a H4:H6 tartományba helyezze el. Hívja meg a Solver programot, töltse ki a felkínált táblázatokat!
| Oldja meg a feladatot, majd adja meg az optimális megoldást!
| Írja be a mezőkbe a jó megoldást! x 1 = x 2 = x 3 = z =
| 2. Oldja meg a következő programozási feladatot, a Solver program segítségével.
| x 1 , x 2 , x 3 ≥ 0 3 x 1 +2 x 3 ≥ 6 2 x 1 + x 2 + x 3 ≤ 15 x 1 + x 2 + x 3 = 8 z=110 x 1 +50 x 2 +70 x 3 → max⁡
| Helyezze el az Excel-táblázaton. Oldja meg, majd válaszoljon a következőkre:
| a) Az optimális megoldás: x1 = x2 = x3 = Zopt=
| b) A változók redukált költsége rendre:
| c) Az erőforrások árnyékára rendre:
| Milyen változást kell megtenni a modellen, hogy a programba be nem került változó is bekerülhessen?
| a) Melyik változó célfüggvénybeli együtthatóját kell megváltoztatni? A . változó
| b) Hogyan kell változtatni az értékét?
| növelni kell
| csökkenteni kell
| c) Legalább mennyivel kell változtatni az értékét?
| d) Mi lesz ezután az optimális megoldás? x 1 = x 2 = x 3 = z =